nclude<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

class Solution {
public:

	int pow1(int c, int secondary)
	{
		int res = 1;
		while (secondary)
		{
		
			res = (res*c) % 1337;
			secondary--;
		}

		return res;
	}
	int superPow(int a, vector<int>& b) {
		int res = 1;
	
		a %= 1337;

		auto it = b.rbegin();
		while (it != b.rend())
		{
			res = (res*pow1(a, *it)) % 1337;
			a = pow1(a, 10);
			it++;
		}
		return res;
	}
};


//三数之和
//深度优先算法+遍历去重，超时间
class Solution {
private:
	int a[3];
	vector<vector<int>> res;
public:
	void dfs(vector<int>& nums1, int step, int i)
	{
		if (step == 3)
		{
			if (a[0] + a[1] + a[2] == 0)
				res.push_back(vector(a, a + 3));
			return;
		}
		for (; i<nums1.size();)
		{
			a[step] = nums1[i];
			if (i + 1 <= nums1.size())
			{
				i += 1;
				dfs(nums1, step + 1, i);
				while (i != 0 && i<nums1.size())
				{
					if (nums1[i] == nums1[i - 1])
						i++;

					else
						break;
				}
			}
			else
				break;
		}
		return;
	}

	vector<vector<int>> threeSum(vector<int>& nums) {
		if (nums.size()<3)
			return res;
		int step1 = 0;
		int j = 0;
		sort(nums.begin(), nums.end());
		dfs(nums, step1, j);
		return res;
	}
};

//双指针，先确定一个数字，然后使用双指针在其后面的范围内寻找满足条件的数字
class Solution {
private:
	vector<vector<int>> res;
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
		if (nums.size()<3)
			return res;

		sort(nums.begin(), nums.end());
		auto it = nums.begin();
		while (it != nums.end())
		{
			if (*it>0)
				break;
			if (it != nums.begin() && *it == *(it - 1))//去掉第一个数相同的情况
			{
				it++;
				continue;
			}

			auto left = it + 1;
			auto right = nums.end() - 1;
			while (left<right)
			{
				if (left<right&&*left + *right>-(*it))
					right--;
				else if (left<right&&*left + *right<-(*it))
					left++;
				else
				{
					res.push_back(vector<int>{*it, *left, *right});
					left++;
					right--;
					while (left<right&&*left == *(left - 1))
						left++;
					while (left<right&&*right == *(right + 1))
						right--;
				}
			}
			it++;
		}
		return res;

	}
};
